package com.tl.test;

/**
 * 二叉搜索树
 */
public class BinaryTree {

	private TreeNode root;
	private int size;

	public BinaryTree() {
	}

	public TreeNode getRoot() {
		return root;
	}

	public void setRoot(TreeNode root) {
		this.root = root;
	}

	public int getSize() {
		return size;
	}

	public void setSize(int size) {
		this.size = size;
	}

	/**
	 * 动态创建二叉树
	 * 
	 * @param value
	 */
	public void insertNode(int value) {
		TreeNode newTreeNode = new TreeNode(value);
		if (root == null) {
			root = newTreeNode;
			setSize(getSize() + 1);
		} else {
			TreeNode currentNode=root;
			while (currentNode != null) {
				if (value == currentNode.getValue()) {
					System.out.println("遇到相同的值了，不做插入!!!");
					return;
				}
				if (value > currentNode.getValue()) {
					if (currentNode.getRightChild() == null) {
						currentNode.setRightChild(newTreeNode);
						setSize(getSize() + 1);
						return;
					} else {
						currentNode = currentNode.getRightChild();
					}
				} else {
					if (currentNode.getLeftChild() == null) {
						currentNode.setLeftChild(newTreeNode);
						setSize(getSize() + 1);
						return;
					} else {
						currentNode = currentNode.getLeftChild();
					}
				}
			}
		}
	}
	
	/**
	 * 先序遍历
	 * 
	 * @param treeNode
	 */
	public void firstTraverseBTree(TreeNode treeNode) {
		if (treeNode != null) {
			System.out.println("" + treeNode.getValue());

			firstTraverseBTree(treeNode.getLeftChild());
			firstTraverseBTree(treeNode.getRightChild());
		}
	}

	/**
	 * 中序遍历
	 * 
	 * @param treeNode
	 */
	public void midTraverseBtrr(TreeNode treeNode) {
		if (treeNode != null) {
			midTraverseBtrr(treeNode.getLeftChild());

			System.out.println("" + treeNode.getValue());

			midTraverseBtrr(treeNode.getRightChild());
		}
	}

	/**
	 * 后序遍历
	 * 
	 * @param treeNode
	 */
	public void lastTraverseBtrr(TreeNode treeNode) {
		if (treeNode != null) {
			lastTraverseBtrr(treeNode.getLeftChild());
			lastTraverseBtrr(treeNode.getRightChild());
			System.out.println("" + treeNode.getValue());
		}
	}

	public static void main(String[] args) {
		int[] intArray = { 6, 5, 3, 9, 8 };
		BinaryTree bsTree = new BinaryTree();
		for (int i : intArray) {
			bsTree.insertNode(i);
		}
		System.out.println(bsTree.size);
//		bsTree.firstTraverseBTree(bsTree.root);
//		bsTree.midTraverseBtrr(bsTree.root);
		bsTree.lastTraverseBtrr(bsTree.root);

	}

}

class TreeNode {
	private TreeNode leftChild;// 左孩子
	private TreeNode rightChild;// 右孩子
	private int value;

	public TreeNode() {
	}

	public TreeNode(int value) {
		this.value = value;
	}

	public TreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(TreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public TreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(TreeNode rightChild) {
		this.rightChild = rightChild;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}
}